%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require Positive integer $n > 1$ and minimum degree $d \geq 1$.
\Ensure Scale-free network on $n$ vertices.
%%
%% algorithm body
\State $G \gets \overline{K_n}$\Comment{vertex set is $V = \{0, 1, \dots, n-1\}$}
\State $M \gets$ list of length $2nd$
\For{$v \gets 0, 1, \dots, n-1$}
  \For{$i \gets 0, 1, \dots, d-1$}
    \State $M[2(vd + i)] \gets v$
    \State $r \gets$ draw uniformly at random from $\{0, 1, \dots, 2(vd + i)\}$
    \State $M[2(vd + i) + 1] \gets M[r]$
  \EndFor
\EndFor
\State add edge $(M[2i],\, M[2i+1])$ to $G$ for $i \gets 0, 1, \dots, nd-1$
\State \Return $G$
\end{algorithmic}
